<!DOCTYPE html>
<html lang="zh-CN">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/myblog/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="/myblog/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="TakCode Blog">
  <meta name="author" content="谢芃">
  <meta name="keywords" content="">
  <title>算法入门 - TakCode</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/5.12.1/css/all.min.css" />
<link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />
<link  rel="stylesheet" href="https://cdn.staticfile.org/mdbootstrap/4.13.0/css/mdb.min.css" />
<link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/3.0.1/github-markdown.min.css" />

<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">



  <link  rel="stylesheet" href="/myblog/lib/prettify/tomorrow-night-eighties.min.css" />

<link  rel="stylesheet" href="/myblog/css/main.css" />


  <link defer rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />


<!-- 自定义样式保持在最底部 -->


<meta name="generator" content="Hexo 4.2.0"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/myblog/">&nbsp;<strong>TakCode</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/myblog/">首页</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/myblog/archives/">归档</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/myblog/categories/">分类</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/myblog/tags/">标签</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/myblog/about/">关于</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/myblog/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
                <p class="mt-3 post-meta">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>
                  星期二, 十一月 12日 2019, 11:32 晚上
                </p>
              

              <p class="mt-1">
                
                  
                  <span class="post-meta">
                    <i class="far fa-chart-bar"></i>
                    4k 字
                  </span>
                

                
                  
                  <span class="post-meta">
                      <i class="far fa-clock"></i>
                      16 分钟
                  </span>
                

                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5 z-depth-3" id="board">
          <div class="post-content mx-auto" id="post">
            
            <div class="markdown-body">
              <p>算法入门</p>
<a id="more"></a>
<p>什么是算法？</p>
<blockquote>
<p>算法是用于解决特定问题的一系列的执行步骤，使用不同的算法，解决同一个问题，效率可能相差非常大</p>
</blockquote>
<p>线性查找：从0到100一个一个去查找。</p>
<p>二分查找：从中间开始查找。</p>
<p>如何评判一个算法的好坏？</p>
<blockquote>
<p>正确性、可读性、健壮性（对不合理输入的反应能力）</p>
<p>时间复杂度：估算程序指令的执行次数（执行时间）</p>
<p>空间复杂度：估算所需占用的存储空间 </p>
</blockquote>
<p>时间复杂度</p>
<blockquote>
<p>对数公式 log3(9) = 2</p>
</blockquote>
<table>
<thead>
<tr>
<th>执行次数</th>
<th>复杂度</th>
<th>非正式术语</th>
</tr>
</thead>
<tbody><tr>
<td>12</td>
<td>O(1)</td>
<td>常数阶</td>
</tr>
<tr>
<td>2n + 3</td>
<td>O(n)</td>
<td>线性阶</td>
</tr>
<tr>
<td>4n^2 + 2n + 6</td>
<td>O(n^2 )</td>
<td>平方阶</td>
</tr>
<tr>
<td>4log₂n + 25</td>
<td>O(logn)</td>
<td>对数阶</td>
</tr>
<tr>
<td>3n + 2nlog₃n + 15</td>
<td>O(nlogn)</td>
<td>nlogn阶</td>
</tr>
<tr>
<td>4n^3 + 3n^2 + 22n + 100</td>
<td>O(n^3 )</td>
<td>立方阶</td>
</tr>
<tr>
<td>2^n</td>
<td>O(2^n )</td>
<td>指数阶</td>
</tr>
</tbody></table>
<p> O(1) &lt; O(logn) &lt; O(n) &lt; O(nlogn) &lt; O(n^2 ) &lt; O(n^3 ) &lt; O(2^n ) &lt; O(n!) &lt; O(n^n ) </p>
<h2 id="斐波那契-fibonacci-number-的实现"><a href="#斐波那契-fibonacci-number-的实现" class="headerlink" title="斐波那契(fibonacci number)的实现"></a>斐波那契(fibonacci number)的实现</h2><pre><code class="js">// 0 1 1 2 3 5 8 13 21 ...
递归实现(性能差) O(2^n)  容易出现栈溢出
function fib1(n) {
    if (n&lt;=1) {return n}
    return a(n - 1) + a(n -2)
}

//O(n)
function fib1(n) {
    if (n&lt;=1) {return n}
    let first = 0;
    let second = 1;
    let sun = 0;
    for (let i = 0; i &lt; n-1; i++) {
        sum = first + second;
        first = second;
        second = sum;
    }return second
}</code></pre>
<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><p>什么是数据结构？</p>
<p>数据结构是计算机存储、组织数据的方式，分为线性结构、树形结构、图形结构</p>
<h3 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h3><p>线性表是具有n个相同类型元素的有限序列（n&gt;=0）</p>
<p><img src="https://www.jianguoyun.com/c/tblv2/ENqDnxLnVDn9GZBmqx4zcIVS8taLVZkIhJQ9fSvJJxjTU_Cr3a3YTlMTTY1LYNKOwhK7B-VY/NumBRkzPTnm9GtqOT9WVOg/l" srcset="/myblog/img/loading.gif" alt=""></p>
<ul>
<li><p>a1 是首节点（首元素）， an 是尾结点（尾元素） </p>
</li>
<li><p>a1 是 a2 的前驱， a2 是 a1 的后继 </p>
<p>常见的线性表有：数组 、链表、栈、队列、哈希表（散列表） </p>
</li>
</ul>
<h3 id="数组结构（Array）"><a href="#数组结构（Array）" class="headerlink" title="数组结构（Array）"></a>数组结构（Array）</h3><p> 数组是一种顺序存储的线性表，所有元素的内存地址是连续的 。</p>
<h3 id="栈结构"><a href="#栈结构" class="headerlink" title="栈结构"></a>栈结构</h3><p>栈是一种非常常见的数据结构，它是一种受限的线性表，后进先出（LIFO）</p>
<p><img src="http://helloxx.cn/1bee2f.jpg" srcset="/myblog/img/loading.gif" alt=""></p>
<h4 id="函数调用栈"><a href="#函数调用栈" class="headerlink" title="函数调用栈"></a>函数调用栈</h4><ul>
<li>函数之间和相互调用：A调用B,B中又调用C,C中又调用D.</li>
<li>那样在执行的过程中，会先将A压入栈，A没有执行完所有不会弹出栈</li>
<li>在A执行的过程中调用了B，会将B压入到栈这个时候B在栈顶A在栈底</li>
<li>如果这个时候B可以执行完，那么B会弹出栈但是B有执行完吗？没有。它调用了C</li>
<li>所以C会压栈，并且在栈顶。而C调用了D,D会压入到栈顶</li>
<li>所以当前的栈顺序是：栈顶A-&gt;B-&gt;C-&gt;D栈顶</li>
<li>D执行完，弹出栈C/B/A依次弹出栈</li>
<li>所以我们有函数调用栈的称呼，就来自于它们內部的实现机制.（通过栈来实现的）</li>
</ul>
<p>面试题：有六个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列？（C）<br>A.543612  B.453216  C.346521  D.234156</p>
<h4 id="基于数组实现栈结构"><a href="#基于数组实现栈结构" class="headerlink" title="基于数组实现栈结构"></a>基于数组实现栈结构</h4><p>push（ element）：添加一个新元素到栈顶位置。<br>pop()：移除栈顶的元素，同时返回被移除的元素。<br>peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）<br>isEmpty()：如果栈里没有任何元素就返回true，否则返回 false。<br>size()：返回栈里的元素个数。这个方法和数组的 length属性很类似。<br>toString()：将栈结构的内容以字符形式返回</p>
<pre><code class="js">function Stack() {
    //栈中的属性
    this.items = []
    //1.将元素入栈
    Stack.prototype.push = function(element) {
        this.items.push(element)
    }
    //2.将元素出栈
    Stack.prototype.pop = function() {
        return this.items.pop()
    }
    //3.返回栈顶元素
    Stack.prototype.peek = function() {
        return this.items[this.items.length - 1]
    }
    //4.判断栈是否为空
    Stack.prototype.isEmpty = function() {
        return this.items.length === 0
    }
    //5.获取栈中元素的个数
    Stack.prototype.push = function() {
        return this.items.length
    }
    //6.toString方法
    Stack.prototype.push = function() {
        var resultString = &#39;&#39;
        for (let i = 0; i &lt; this.items.length; i++) {
            resultString += this.items[i] + &#39; &#39;
        } return resultString
    }
}</code></pre>
<h4 id="十进制转二进制"><a href="#十进制转二进制" class="headerlink" title="十进制转二进制"></a>十进制转二进制</h4><p>要把十进制转化成二进制，可以将该十进制数字和2整除，直到结果是0为止</p>
<pre><code class="js">function decTwobin(dec) {
    //定义栈对象
    var stack = new Stack() //Stack为上面定义的函数
    //循环操作
    while (dec &gt; 0) {
        //获取余数，并且放入到栈中
        stack.push(dec % 2)
        //获取整除后的结果，作为下一次运行的数字
        dec = Math.floor(dec /2 )
    }
    //从栈中取出0和1
    var binaryString = &#39;&#39;
    while(!stack.isEmpty()) {
        binaryString += stack.pop()
    } return binaryString
}</code></pre>
<h3 id="队列结构"><a href="#队列结构" class="headerlink" title="队列结构"></a>队列结构</h3><p>队列是一种非常常见的数据结构，它是一种受限的线性表，先进先出（FIFO  First In First Out），比如排队</p>
<p>受限之处在于只允许在表的前端进行删除操作，在表的后端进行插入操作</p>
<h4 id="基于数组实现队列"><a href="#基于数组实现队列" class="headerlink" title="基于数组实现队列"></a>基于数组实现队列</h4><p>enqueue(element)：添加一个新元素到队列尾部。<br>dequeue()：移除队列头部的元素，同时返回被移除的元素。<br>front()：返回队列头部的元素，不对队列做任何修改（这个方法不会移除队列的元素，仅仅返回它）<br>isEmpty()：如果队列里没有任何元素就返回true，否则返回 false。<br>size()：返回队列里的元素个数。这个方法和数组的 length属性很类似。<br>toString()：将队列结构的内容以字符形式返回</p>
<pre><code class="js">function Queue() {
    //属性
    this.items = []
    //方法
    //添加元素到列队尾部
    Queue.prototype.enqueue = function(element) {
        this.items.push(element)
    }
    //删除队列头部元素
    Queue.prototype.dequeue = function() {
        return this.items.shift()
    }
    //查看头部元素
    Queue.prototype.front = function() {
        return this.items[0]
    }
    //查看队列是否为空
    Queue.prototype.isEmpty = function() {
        return this.items.length === 0
    }
    //查看队列中元素的个数
    Queue.prototype.size = function() {
        return this.items.length
    }
    //以字符串形式返回
    Queue.prototype.toString = function() {
        var resultString = &#39;&#39;
        for (var i = 0; i &lt; this.items.length; i++) {
            resultString += this.items[i] + &#39; &#39;
        } return resultString
    }
}</code></pre>
<h4 id="击鼓传花-面试题"><a href="#击鼓传花-面试题" class="headerlink" title="击鼓传花(面试题)"></a>击鼓传花(面试题)</h4><pre><code class="js">function passGame(nameList, num) {
    //创建一个队列结构
    var queue = new Queue() //Queue为上面定义的函数
    //将所有人依次加入到队列中
    for (var i = 0; i &lt; nameList.length; i++) {
        queue.enqueue(nameList[i])
    }
    //开始数数字
    while(queue.size() &gt; 1) {
        //不是num的时候，重新加入到队列的末尾
        //是num这个数字的时候，将其从队列中删除
        //num数字之前的人重新放到队列的末尾
        for(var i = 0; i &lt; num-1; i++) {
            queue.enqueue(queue.dequeue())
        }
        //对应num的这个人，直接从队列中删除
        queue.dequeue()
    }
    //获取剩下的那个人
    var endName = queue.front()
    console.log(&#39;最终剩下的人：&#39; + endName )
    console.log(&#39;该人之前的下标为：&#39; + nameList.indexOf(endName))
}</code></pre>
<h4 id="优先级队列"><a href="#优先级队列" class="headerlink" title="优先级队列"></a>优先级队列</h4><p>优先级队列是在插入一个元素的时候，会考虑该数据的优先级，先和其它数据比较优先级，比较完成后，可以得出这个元素在队列中正确位置。</p>
<p>实现优先级队列主要考虑的问题：</p>
<ul>
<li>每个元素不再只是一个数据，而且包含数据的优先级</li>
<li>在添加方式中，根据优先级放入正确的位置</li>
</ul>
<pre><code class="js">function PriorityQueue() {
    //创建一个内部函数
    function QueueElement(element, priority) {
        this.element = element
        this.priority = priority
    }
    //封装属性
    this.items = []
    //实现插入方法
    PriorityQueue.prototype.enqueue = function (element, priority) {
        //创建一个QueueElement对象
        var queueElement = new QueueElement(element, priority)
        //判断队列是否为空
        if(this.items.length === 0) {
            this.items.push(queueElement)
        } else {
            var added = false
            for  (var i = 0; i &lt; this.items.length; i++) {
                if (queueElement.priority &lt; this.items[i].priority) {
                    this.items.splice(i, 0, queueElement)
                    added = trut
                    break
                }
            }
            if (!added) {
                this.items.push(queueElement)
            }
        }
    }
    //删除队列头部元素
    PriorityQueue.prototype.dequeue = function() {
        return this.items.shift()
    }
    //查看头部元素
    PriorityQueue.prototype.front = function() {
        return this.items[0]
    }
    //查看队列是否为空
    PriorityQueue.prototype.isEmpty = function() {
        return this.items.length === 0
    }
    //查看队列中元素的个数
    PriorityQueue.prototype.size = function() {
        return this.items.length
    }
    //以字符串形式返回
    PriorityQueue.prototype.toString = function() {
        var resultString = &#39;&#39;
        for (var i = 0; i &lt; this.items.length; i++) {
            resultString += this.items[i].element + &#39;-&#39; + this.items[i].priority + &#39; &#39;
        } return resultString
    }
}
var s = new PriorityQueue()
s.enqueue(&#39;a&#39;, 1)
s.enqueue(&#39;cc&#39;, 20)
s.enqueue(&#39;sf&#39;, 33)
s.enqueue(&#39;sdfs&#39;, 2)
s.enqueue(&#39;wer&#39;, 90)
s.enqueue(&#39;sdfsd&#39;, 6)
console.log(s.toString())
</code></pre>
<h3 id="链表结构"><a href="#链表结构" class="headerlink" title="链表结构"></a>链表结构</h3><p>链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。</p>
<p><strong>数组:</strong> </p>
<blockquote>
<p>要存储多个元素，数组（或列表）可能是最常用的数据结构。</p>
<p>我们之前说过, 几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便，提供了一个便利的<code>[]</code>语法来访问它的元素。</p>
</blockquote>
<p>但是数组也有很多缺点: </p>
<ul>
<li>数组的创建通常需要申请一段连续的内存空间(一整块的内存), 并且大小是固定的(大多数编程语言数组都是固定的), 所以当当前数组不能满足容量需求时, 需要扩容. (一般情况下是申请一个更大的数组, 比如2倍. 然后将原数组中的元素复制过去)</li>
<li>而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的位移.</li>
<li>尽管我们已经学过的JavaScript的<code>Array</code>类方法可以帮我们做这些事，但背后的原理依然是这样 。</li>
</ul>
<p><strong>链表</strong> </p>
<blockquote>
<p>要存储多个元素, 另外一个选择就是使用链表.</p>
<p>但不同于数组, 链表中的元素在内存中不必是连续的空间.</p>
<p>链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.</p>
</blockquote>
<ul>
<li>相对于数组, 链表有一些优点: <ul>
<li>内存空间不是必须连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.</li>
<li>链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.</li>
<li>链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.</li>
</ul>
</li>
<li>相对于数组, 链表有一些缺点: <ul>
<li>链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).</li>
<li>无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的问题.</li>
</ul>
</li>
</ul>
<p><img src="http://helloxx.cn/110203.jpg" srcset="/myblog/img/loading.gif" alt=""></p>
<p> 链表常见操作</p>
<ul>
<li>append(element)：向列表尾部添加一个新的项</li>
<li>insert(position, element)：向列表的特定位置插入一个新的项。</li>
<li>get(position): 获取对应位置的元素</li>
<li>indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回<code>-1</code>。</li>
<li>update(position,element): 修改某个位置的元素</li>
<li>removeAt(position)：从列表的特定位置移除一项。</li>
<li>remove(element)：从列表中移除一项。</li>
<li>isEmpty()：如果链表中不包含任何元素，返回<code>true</code>，如果链表长度大于0则返回<code>false</code>。</li>
<li>size()：返回链表包含的元素个数。与数组的<code>length</code>属性类似。</li>
<li>toString()：由于列表项使用了<code>Node</code>类，就需要重写继承自JavaScript对象默认的<code>toString</code>方法，让其只输出元素的值。</li>
</ul>
<pre><code class="js">//封装链表类
function LinkedList() {
  //内部方法，节点类
  function Node(data) {
    this.data = data
    this.next = null
  }
  //属性
  this.head = null
  this.length = 0
  //添加新的项
  LinkedList.prototype.apped = function(data) {
    //创建新节点
    var newNode = new Node(data)
    //判断是否添加的是第一个节点
    if(this.length === 0) {
      this.head = newNode
    } else {
      //找到最后一个节点
      var current = this.head 
      while (current.next) {
        current = current.next
      }
      //最后节点的next指向新的节点
      current.next = newNode
    }
    //长度加1
    this.length += 1
  }

  // 链表的 tostring方法
  LinkedList.prototype.toString = function(){
    // 1.定义两个变量
    var current = this.head
    var listString = &quot;&quot;
    //2.环获取链表中所有的元素
    while(current){
      listString +=&quot;,&quot;+ current.data +&quot; &quot;
      current=current.next
    }
    // 3.返回最终结果
    return listString.slice(1)
  }

  // insert方法
  LinkedList.prototype.insert = function(position, data){
    // 1、对 position进行越界判断 不能传负数
    // 2、对长度进行判断
    if(position&lt;0 || position &gt; this.length ) return false
    // 3、根据data创建newNode
    var newNode = new Node(data)
    // 判断插入的位置是否是第一个
    if(position == 0){
      newNode.next = this.dead
      this.head = newNode
    }else {
      var index = 0
      // 作为初始节点
      var current = this.head
      var previous = null
      // 循环 直到找到为止
      while(index++&lt;position){
        previous = current
        current = current.next
      }
      newNode.next = current
      previous.next = newNode
    }
    this.length+=1
    return true
  }

 // get方法
  LinkedList.prototype.get = function(position){
    // 1.越界判断
    if(position&lt;0|| position&gt;= this.length) return null
    // 2. 获取对应的data
    var current = this.head
    var index = 0
    while (index++ &lt; position){
      current = current.next
    }
    return current.data
  }

  // indexOf方法
  LinkedList.prototype.indexOf = function(data){
    var current = this.head
    var index = 0
    // 开始查找
    while(current){
      if(current.data == data){
        return index
      }
      current = current.next
      index +=1      
    }
    // 找到最后没有找到，返回-1
    return -1
  }

  // update 方法
  LinkedList.prototype.update = function(position,newData){
    // 越界判断
    if(position&lt;0|| position&gt;=this.length) return false
    // 查找到正确的节点
    var current = this.dead
    var index = 0
    while (index++&lt;position){
      current = current.next
    }
    // 将position位置的node的data修改成newData
    current.data = newData
    return true
  }

  // removeAt 方法
  LinkedList.prototype.removeAt = function(position){
    // 越界判断
    if(position&lt;0|| position&gt;=this.length) return false
    // 判断是否删除的是第一个节点 可以试试length -1 的方法
    var current = this.head
    if(position==0){
      this.head = this.head.next
    }else{
      var index = 0
      var previous = null
      while(index++&lt;position){
        previous = current
        current = current.next
      }
      previous.next = current.next
    }
    this.length -= 1
    return current.data
  }

  // removeAt 方法
  LinkedList.prototype.remove = function(data){
    // 获取data 在列表中的位置
    var position = this.indexOf(data)
    // 根据位置信息删除节点
        return this.removeAt(position)    
  }

  // isEmmty方法
  LinkedList.prototype.remove = function(){
    return this.length==0
  }

  // size方法
  LinkedList.prototype.remove = function(data){
      return this.length
  }
}


// 测试代码
var list = new LinkedList()

list.append(&#39;abc&#39;)
list.append(&#39;cba&#39;)
list.append(&#39;nnn&#39;)
console.log(list)
list.insert(0,&#39;aaa&#39;)
list.insert(3,&#39;bbb&#39;)
list.insert(5,&#39;ccc&#39;)
console.log(list)

console.log(list.get(0))
console.log(list.get(2))
console.log(list.get(5))

console.log(list.indexOf(&#39;abc&#39;))
console.log(list.indexOf(&#39;bbb&#39;))
console.log(list.indexOf(&#39;123&#39;))
//update测试
list.update(0,&#39;mmmm&#39;)
list.update(3,&#39;3333&#39;)
console.log(list)
//removeAt 测试
list.removeAt(0)
list.removeAt(3)
//remove 测试
list.remove(&#39;nnn&#39;)
list.remove(&#39;abc&#39;)

// isEmpty / size 测试
alert(this.isEmpty())
alert(this.size())
</code></pre>
<p><img src="C:%5CUsers%5CXP%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200827233806361.png" srcset="/myblog/img/loading.gif" alt="image-20200827233806361"></p>
<h3 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h3><h4 id="单向链表"><a href="#单向链表" class="headerlink" title="单向链表"></a>单向链表</h4><p>只能从头遍历到尾或者从尾遍历到头(一般从头到尾）<br>也就是链表相连的过程是单向的，实现的原理是上一个链表中有一个指向下一个的引用<br>单向链表有一个比较明显的缺点：<br>我们可以轻松的到达下一个节点，但是回到前一个节点是很难的。但是，在实际开发中，经常会遇到需要回到上一个节点的情况<br>举个例子：假设一个文本编辑用链表来存储文本。每一行用一个 String对象存储在链表的一个节点中，当编辑器用户向下移动光标时，链表直接操作到下一个节点即可。但是当用户将光标向上移动呢？这个时候为了回到上一个节点我们可能需要从first开始，依次走到想要的节点上</p>
<h4 id="双向链表-1"><a href="#双向链表-1" class="headerlink" title="双向链表"></a>双向链表</h4><p>既可以从头遍历到尾，又可以从尾遍历到头<br>也就是链表相连的过程是双向的。<br>一个节点既有向前连接的引用，也有一个向后连接的引用。<br>双向链表可以有效的解决单向链表中提到的问题<br>双向链表的缺点<br>每次在插入或删除某个节点时，需要处理四个节点的引用，而不是两个。也就是实现起来要困难一些<br>并且相当于单向链表，必然占用内存空间更大一些<br>但是这些缺点和我们使用起来的方便程度相比，是微不足道的</p>

            </div>
            <hr>
            <div>
              <p>
                
                
              </p>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/myblog/2020/01/04/%E5%9B%BE%E8%A7%A3HTTP%E7%AC%94%E8%AE%B0/">
                        <i class="fa fa-chevron-left"></i>
                        <span class="hidden-mobile">图解HTTP学习笔记</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/myblog/2019/09/15/Nodejs+MongoDB%E7%AC%94%E8%AE%B0/">
                        <span class="hidden-mobile">Node学习笔记</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="fa fa-chevron-right"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

              
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc-start"></div>
<div id="toc">
  <p class="h5"><i class="far fa-list-alt"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    </div>
    

    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/popper.js/1.16.1/umd/popper.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="https://cdn.staticfile.org/mdbootstrap/4.13.0/js/mdb.min.js" ></script>
<script  src="/myblog/js/main.js" ></script>


  <script  src="/myblog/js/lazyload.js" ></script>



  
  <script  src="https://cdn.staticfile.org/tocbot/4.10.0/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var navHeight = $('#navbar').height();
      var toc = $('#toc');
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;
      var tocLimMax = 2 * boardTop + boardCtn.height();

      $(window).scroll(function () {
        var tocLimMin = $('#toc-start').offset().top - navHeight;
        var scroH = document.body.scrollTop + document.documentElement.scrollTop;

        if (tocLimMin <= scroH && scroH <= tocLimMax) {
          toc.css({
            'display': 'block',
            'position': 'fixed',
            'top': navHeight,
          });
        } else if (scroH <= tocLimMin) {
          toc.css({
            'position': '',
            'top': '',
          });
        } else if (scroH > tocLimMax) {
          toc.css('display', 'none');
        }
      });
      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '.post-content',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc > p').css('visibility', 'visible');
      }
      var offset = boardCtn.css('margin-right')
      $('#toc-ctn').css({
        'right': offset
      })
    });
  </script>





  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/myblog/js/clipboard-use.js" ></script>








<!-- Plugins -->



  <script  src="https://cdn.staticfile.org/prettify/188.0.0/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "算法入门&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/myblog/js/local-search.js" ></script>
  <script>
    var path = "/myblog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script defer src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>












</body>
</html>
